package seqlist.link;

import seqlist.SeqList;

import java.util.Stack;

/**
 * @author yuisama
 * @date 2023/03/16 20:26
 * 递归的实现单链表
 **/
public class SingleLinkedListR<E> implements SeqList<E> {
    private class Node {
        E val;
        Node next;
        public Node(E val) {
            this.val = val;
        }
    }
    private Node head;
    private int size;
    @Override
    public void add(E element) {
        add(size,element);
    }

    @Override
    public void add(int index, E element) {
        head = addInternal(head,index,element);
    }
    // 在当前以head为头节点的链表中，在索引index位置插入一个新的值element
    // 插入后返回新的链表头结点
    private Node addInternal(Node head, int index, E element) {
        // 1.base case
        if (index == 0) {
            // 头插
            Node node = new Node(element);
            node.next = head;
            head = node;
            size ++;
            return head;
        }
        // index不在头结点插入
        head.next = addInternal(head.next,index - 1,element);
        return head;
    }

    @Override
    public E removeByIndex(int index) {
        return null;
    }

    @Override
    public void removeByValue(E element) {

    }

    @Override
    public void removeAllValue(E element) {

    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public boolean contains(E element) {
        return false;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }

    public void print() {
        print(head);
    }
    // 传入一个以head为头节点的链表，就能按顺序输出每个节点的值
    private void print(Node head) {
        // 1.base case
        if (head == null) {
            System.out.print("NULL\n");
            return;
        }
        // 已知的只有head
        System.out.print(head.val + "->");
        // 从第二个节点开始的打印交给子函数
        print(head.next);
    }

    public void printReverse() {
        printReverse(head);
    }
    // 传入一个以head为头节点的链表，就能从最后一个节点开始逆序输出链表的每个节点
    int count = 0;
    private void printReverse(Node head) {
        // 1.base case
        if (head == null) {
            return;
        }
        count ++;
        // 链表有节点 head
        // 先将以head.next为头节点的子链表逆序输出之后再输出头节点
        printReverse(head.next);
        count --;
        // 走到这里，可以放心的输出头节点~
        System.out.print(head.val + "->");
        if (count == 0) {
            System.out.print("NULL");
        }
    }
    // 链表的逆置输出，借助栈
    public void printReverseNonRecursion() {
        Stack<Node> stack = new Stack<>();
        // 遍历原链表
        Node temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop().val + " ");
        }
    }
}